package com.example.system.class05;

import java.util.Arrays;

/**
 * @Date 2022/7/21
 * @Created by Jonathan
 */
public class Code01_MergeSort {
    public static void main(String[] args) {
        int[] arr = new int[]{3, 1, 2, 4, 9, 5, 6, 3};
        //mergeSort(arr);
        mergeSort2(arr);
        System.out.println(Arrays.toString(arr));
    }


    /**
     * N*logN
     *
     * @param arr
     */
    private static void mergeSort(int[] arr) {
        int L = 0;
        int R = arr.length - 1;
        process(arr, L, R);
    }

    /**
     * 合并两个两个有序数组
     */
    private static void merge(int[] arr, int L, int M, int R) {
        int[] help = new int[R - L + 1];
        int index = 0;
        int p1 = L; // 移动的左指针
        int p2 = M + 1; // 移动的右指针
        while (p1 <= M && p2 <= R) {
            help[index++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
        }
        // 有且仅有一个越界
        while (p1 <= M) {
            help[index++] = arr[p1++];
        }

        while (p2 <= R) {
            help[index++] = arr[p2++];
        }
        // 再拷贝回去
        for (int i = 0; i < help.length; i++) {
            arr[L + i] = help[i];
        }

    }


    private static void process(int[] arr, int L, int R) {
        // 只有一个数就结束
        if (L == R) {
            return;
        }
        int M = L + ((R - L) >> 1);
        // 左边有序  右边有序
        process(arr, L, M);
        process(arr, M + 1, R);
        // 将两边的合并起来
        merge(arr, L, M, R);
    }

    // 归并的非递归实现
    public static void mergeSort2(int[] arr) {
        int N = arr.length;
        int step = 1; // 步长
        // 步长为1 干完事儿了  步长为2的继续...
        while (step < N) {
            int L = 0;
            while (L < N) {
                // 左边界的要是不够 就不会进入while循环
                int M = L + step - 1;
                // 后面的位置可能会不够
                if (M >= N) {
                    break;
                }
                // 右组的位置也可能不够
                int R = Math.min(M + step, N - 1);
                merge(arr, L, M, R);
                L = R + 1;
            }
            // 防止溢出
            if (step > N / 2) {
                break;
            }
            step <<= 1;
        }
    }

}
